1. Field of the Invention
The present invention relates to an apparatus and method for generating a random number.
2. Description of the Prior Art
Random number generators are essential components for a wide range of applications. In security systems they provide the secret keys or tokens for authentication and encryption. They are also applied to various problems in simulation software.
For such applications, it is a key requirement to provide a high quality random number source. A true random number is a collection of bits that are unpredictable and show statistical properties of randomness.
A number of hardware techniques have been developed for generating random numbers, such techniques typically using a physical source of randomness within a data processing apparatus. Such circuits are often referred to as True Random Number Generators (TRNGs).
As an example of such a TRNG circuit, the article “True Random Number Generator with a Metastability-Based Quality Control” by C Tokunaga et al, IEEE Journal of Solid-State Circuits, Volume 43, No. 1, January 2008, pages 78-85, describes a design of TRNG that uses a latch placed into a metastable state, i.e. where its stored state is indeterminate, lying between a logic zero and a logic one level. Over time, such a latch placed in a metastable state will resolve to either a logic zero value or a logic one value, with noise contributing to the direction in which the latch resolves. The circuit described in this paper monitors the time taken to resolve to a known value within the latch, this time being unknown and effectively random. That resolving time is then converted into a random number.
The article “A High-Speed Oscillator-Based Truly Random Number Source for Cryptographic Applications on a Smart Card IC” by M Bucci et al, IEEE Transactions on Computers, Volume 52, No. 4, April 2003, describes an oscillator-based random number generator, where a low frequency oscillator samples a fast oscillator in a D flip-flop. If the low frequency oscillator period features a standard deviation much greater than the faster oscillator period, the states of the sampled oscillator in two successive sampling times can be assumed uncorrelated (i.e. independent), thus generating a random bit stream. The oscillator described in the article is provided with an amplified noise source, yielding a standard deviation of about 10% of the period length. Such a high jitter level improves the quality of the random stream.
The article “Ring Oscillator Based Random Number Generator Utilizing Wake-Up Time Uncertainty” by T Nakura et al, IEEE Asian Solid-State Circuits Conference, Nov. 16-18, 2009, Taipei, Taiwan, pages 121-124, describes a random number generation circuit that utilises a ring oscillator's wake-up time uncertainty to generate a random number. In particular, a ring oscillator goes into metastability state before starting to oscillate when its control voltage is increased from zero. The metastability causes an uncertainty in the wake-up time of the ring oscillator resulting in large jitter, which is then used for random number generation.
The article “Power-Up SRAM State as an Identifying Fingerprint and Source of True Random Numbers” by D Holcomb et al, IEEE Transactions on Computers, Volume 58, No. 9, September 2009, pages 1198-1210, describes a technique which uses the initial state of an SRAM as a source of a random number. However, one problem with this approach is that the skew due to process variation will always be present, and hence whilst such an approach may be good for generating deterministic chip identifiers, it is less good for random number generation, since successive generation of the random number will be more or less identical.
All of the various prior art random number generators described above are relatively complex and occupy a significant area, making them impractical for many implementations. Further, to the extent they include analog circuits, they will give rise to layout constraints, and may not be readily portable between different process geometries. Hence, as process geometries shrink, and the individual components hence get smaller, such techniques would require at least a degree of redesign to enable them to be applied to such new process geometries.
Accordingly, it would be desirable to provide an improved mechanism for generating true random numbers.